package com.sakura.动态规划;

import java.util.Arrays;

public class Code639_解码方法II {

    // 暴力递归
    public int numDecodings1(String s) {
        return f1(s.toCharArray(), 0);
    }

    public int f1(char[] s, int i) {
        if (i == s.length) {
            return 1;
        }
        int ans = f1(s, i + 1) * (s[i] == '*' ? 9 : 1);
        if (i + 1 < s.length) {
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    // 两个都是 1 .... 9
                    if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
                        ans += f1(s, i + 2);
                    }
                } else {
                    // i: [1..9] i + 1: *
                    if (s[i] == '1') {
                        ans += 9 * f1(s, i + 2);
                    }
                    if (s[i] == '2') {
                        ans += 6 * f1(s, i + 2);
                    }
                }
            } else {
                // i: *
                if (s[i + 1] != '*') {
                    if (s[i + 1] <= '6') {
                        ans += 2 * f1(s, i + 2);
                    } else {
                        ans += f1(s, i + 2);
                    }
                } else {
                    ans += 15 * f1(s, i + 2);
                }
            }
        }
        return ans;
    }

    // 记忆化搜索
    public static long mod = 1000000007;
    public int numDecodings2(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        long[] dp = new long[n + 1];
        Arrays.fill(dp, -1);
        return (int) f2(s, 0, dp);
    }

    private long f2(char[] s, int i, long[] dp) {
        if (i == s.length) {
            return 1;
        }
        if (s[i] == '0')return 0;
        if (dp[i] != -1) {
            return dp[i];
        }
        long ans = f2(s, i + 1, dp) * (s[i] == '*' ? 9 : 1);
        if (i + 1 < s.length) {
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    // 两个都是 1 .... 9
                    if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
                        ans += f2(s, i + 2, dp);
                    }
                } else {
                    // i: [1..9] i + 1: *
                    if (s[i] == '1') {
                        ans += 9 * f2(s, i + 2, dp);
                    }
                    if (s[i] == '2') {
                        ans += 6 * f2(s, i + 2, dp);
                    }
                }
            } else {
                // i: *   i + 1: [1..9]
                if (s[i + 1] != '*') {
                    if (s[i + 1] <= '6') {
                        ans += 2 * f2(s, i + 2, dp);
                    } else {
                        ans += f2(s, i + 2, dp);
                    }
                } else {
                    // i: * i + 1: *
                    ans += 15 * f2(s, i + 2, dp);
                }
            }
        }
        ans %= mod;
        dp[i] = ans;
        return ans;
    }
}
